from typing import *
from math import inf
from heapq import heappop, heappush


class Solution:

    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int,
                           destination: int, target: int) -> List[List[int]]:
        nexts = [[] for _ in range(n)]  # 无向图邻接
        ws = [[inf] * n for _ in range(n)]  # 边权值
        for i, (a, b, w) in enumerate(edges):
            nexts[a].append((b, i))
            nexts[b].append((a, i))
            ws[a][b] = ws[b][a] = w
        d1 = [inf] * n  # 抵达最短距离
        q = [(0, source)]  # 从source开始

        while q:
            d, s = heappop(q)
            if d < d1[s]:
                d1[s] = d
                for next, i in nexts[s]:
                    t = 1 if ws[s][next] == -1 else ws[s][next]
                    if d + t < d1[next]:
                        heappush(q, (d + t, next))
        if d1[destination] > target:
            return []
        d2 = [inf] * n  # 抵达最短距离
        q = [(0, source)]  # 从source开始
        while q:
            d, s = heappop(q)
            if d < d2[s]:
                d2[s] = d
                for next, i in nexts[s]:
                    t = ws[s][next]
                    if ws[s][next] == -1:
                        t = max(1, target - d1[destination] + d1[next] - d2[s])
                    if d + t < d2[next]:
                        edges[i][2] = t
                        heappush(q, (d + t, next))
        if d2[destination] < target:
            return []
        for i in range(len(edges)):
            if edges[i][2] == -1:
                edges[i][2] = 1

        return edges


so = Solution()
print(
    so.modifiedGraphEdges(5, [[4, 1, -1], [2, 0, -1], [0, 3, -1], [4, 3, -1]],
                          0, 1, 5) == [[4, 1, 1], [2, 0, 3], [0, 3, 3], [4, 3, 1]])
print(
    so.modifiedGraphEdges(
        5, [[1, 2, 1], [0, 1, 1], [0, 4, -1], [4, 3, -1], [3, 2, -1]], 2, 0,
        2) == [[1, 2, 1], [0, 1, 1], [0, 4, 1], [4, 3, 1], [3, 2, 1]])
print(
    so.modifiedGraphEdges(n=5,
                          edges=[[4, 1, -1], [2, 0, -1], [0, 3, -1],
                                 [4, 3, -1]],
                          source=0,
                          destination=1,
                          target=5) == [[4, 1, 1], [2, 0, 3], [0, 3, 3], [4, 3, 1]])
